1283F - DIY Garland - CodeForces Solution

  #include <bits/stdc++.h> 
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 #define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

ll INF=2e15;


int main() {
    ios::sync_with_stdio(false);
  cin.tie(0);

ll n;cin>>n;
vector<ll> a(n-1);
for(ll i=0;i<n-1;i++) cin>>a[i];

ll root=a[0];
ll now=root;

vector<bool> note(n+10);
note[root]=true;

vector<pair<ll,ll>> ans;
ll ind=1;

for(ll i=n;i>=1;i--) {
  if(note[i]) continue;

while(ind<n-1&&!note[i]) {
  if(!note[a[ind]]) {
    ans.push_back(make_pair(now,a[ind]));
    note[a[ind]]=true;
    now=a[ind];
  }

  else {
    ans.push_back(make_pair(now,i));
    note[i]=true;
    now=a[ind];
  }
  ind++;
}

if(ind==n-1&&!note[i]) {
  ans.push_back(make_pair(now,i));
  note[i]=true;

}

if(!note[i]) {
  cout<<-1<<endl;
  return 0;
}


}

cout<<root<<endl;
for(auto x:ans) cout<<x.first<<" "<<x.second<<endl;
}